package Arithmetic;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 34255
 * Date: 2024-11-04
 * Time: 21:37
 */
//二分查找
public class BinarySearch {
    //34.在排序数组中查找元素的第一个和最后一个位置

    /**
     * 时间复杂度：O(logN)
     * 空间复杂度：O(1)
     * @param nums 目标数组
     * @param target 目标值
     * @return 下标位置
     */
    public static int[] searchRange(int[] nums, int target) {
        int first = findFirst(nums,target);
        if(first == nums.length || nums[first] != target) return new int[]{-1,-1};
        int last = findFirst(nums,target + 1) - 1;
        return new int[]{first,last};
    }

    public static int findFirst(int[] nums, int target){
        //定义左右指针
        int left = 0;
        int right = nums.length - 1;

        //循环不变量:[ ]
        while(left <= right){
            int mid = left + (right - left);//防止溢出
            if(nums[mid] < target) left += 1;
            else right -= 1;
        }
        return left;
    }

    //LCR 072.X的平方根

    /**
     * 时间复杂度:O(log46340)
     * 空间复杂度:O(1)
     * @param x 目标值
     * @return X的平方根
     */
    public static int mySqrt(int x) {
        //定义左右指针
        int left = 0;
        int right = 46340;

        while(left <= right){
            int mid = left + (right - left) / 2;
            if(mid * mid < x) left = mid + 1;
            else if(mid * mid > x) right = mid - 1;
            else return mid;
        }
        //没找到，返回整数部分
        return right;
    }

    //LCR 173.点名

    /**
     * 时间复杂度：O(logN)
     * 空间复杂度：O(1)
     * @param nums 目标数组
     * @return 缺失的数字
     */
    public static int takeAttendance(int[] nums) {
        //定义双指针
        int left = 0;
        int right = nums.length - 1;

        //循环不变量：左闭右闭
        while(left <= right){
            int mid = left + (right - left) / 2;//防止溢出
            if(mid == nums[mid]){//下标与值一致
                left = mid + 1;
            }else{//下标与值不一致
                right = mid - 1;
            }
        }
        return left;
    }

    //LCR 068.搜索插入位置

    /**
     * 时间复杂度：O(logN)
     * 空间复杂度：O(1)
     * @param nums 目标数组
     * @param target 目标值
     * @return 插入的下标位置
     */
    public static int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        //循环不变量: 左闭右闭
        while(left <= right){
            int mid = left + (right - left) / 2;//防止溢出
            if(nums[mid] < target) left = mid + 1;
            else if(nums[mid] > target) right = mid - 1;
            else return mid;
        }
        return left;
    }

    //153.寻找旋转排序数组中的最小值

    /**
     * 时间复杂度：O(logN)
     * 空间复杂度：O(1)
     * @param nums 旋转数组
     * @return 最小值
     */
    public static int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int D = nums[right];//记录D值

        //循环不变量：[ ]
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] <= D){//说明Mid位于C~D区间
                right = mid - 1;
            }else{//说明Mid位于A~B区间
                left = mid + 1;
            }
        }
        return nums[left];
    }

    //852.山脉数组的峰顶索引

    /**
     * 时间复杂度：O(logN)
     * 空间复杂度：O(1)
     * @param arr 数组
     * @return 峰值下标
     */
    public static int peakIndexInMountainArray(int[] arr) {
        int left = 1;
        int right = arr.length - 2;

        //循环不变量：[ ]
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1] ){//找到峰值
                return mid;
            }else if(arr[mid] < arr[mid + 1]){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return -1;
    }

    //162.寻找峰值

    /**
     * 时间复杂度：O(logN)
     * 空间复杂度：O(1)
     * @param nums 数组
     * @return 峰值元素下标
     */
    public static int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 2;

        //循环不变量：[]
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[mid + 1]){//说明右区间至少一个峰值
                left = mid + 1;
            }else{//说明左区间至少一个峰值
                right = mid - 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        //34.在排序数组中查找元素的第一个和最后一个位置
        int[] array1 = {5,7,7,8,8,10};
        int[] ret = searchRange(array1,8);
        System.out.println(Arrays.toString(ret));

        //LCR 072.X的平方根
        int sqrtNum = mySqrt(8);
        System.out.println(sqrtNum);

        //LCR 173.点名
        int[] array2 = {0,1,2,3,4};
        int num = takeAttendance(array2);
        System.out.println(num);

        //LCR 068.搜索插入位置
        int[] array3 = {1,3,5,6};
        int insertIndex = searchInsert(array3,2);
        System.out.println(insertIndex);

        //153.寻找旋转排序数组中的最小值
        int[] array4 = {1};
        int minIndex = findMin(array4);
        System.out.println(minIndex);

        //852.山脉数组的峰顶索引
        int[] array5 = {0,2,3,4,5,3,2,1};
        int index = peakIndexInMountainArray(array5);
        System.out.println(index);

        //162.寻找峰值
        int[] array6 = {1,2,3,1};
        int peakIndex = findPeakElement(array6);
        System.out.println(peakIndex);
    }
}
